package slidingwindows.leetcode.editor.cn;

import java.util.HashMap;
import java.util.Map;

/**
 * @Author: Dang Qi
 * @Date: 2021/2/10  14:57
 * @Description: 567. 字符串的排列
 */
public class PermutationInString {
    public static void main(String[] args) {
        Solution solution = new PermutationInString().new Solution();
        String s1 = "abcdxabcde";
        String s2 = "abcdeabcdx";
        System.out.println(solution.checkInclusion(s1, s2));
    }
    class Solution {
        public boolean checkInclusion(String s1, String s2) {
            int left=0, right=0;
            int num = 0;
            //用来记录s1中各个字符出现的次数
            Map<Character, Integer> target = new HashMap<>();
            for(int i=0; i<s1.length(); i++){
                char c = s1.charAt(i);
                if(target.get(c)==null)
                    target.put(c, 1);
                else target.put(c, target.get(c)+1);
            }
            while(right<s2.length()){
                char c = s2.charAt(right);
                Integer cNum = target.get(c);
                //如果当前字符在s1中存在并且剩余填充数量大于0
                if(cNum!=null && cNum>0){
                    target.put(c, cNum-1);
                    if(cNum-1==0) {
                        num++;
                        if(num==target.size()) return true;
                    }
                    right++;
                }
                // 如果当前字符不是s1中的字符，移动左指针，在移动过程中恢复target的值
                else if(cNum == null){
                    right++;
                    while(left<right){
                        char t = s2.charAt(left++);
                        Integer tN = target.get(t);
                        if(tN!=null){
                            num -= (tN==0?1:0);
                            target.put(t, tN+1);
                        }
                    }
                }else if(cNum==0){
                    char t = s2.charAt(left++);
                    Integer tN = target.get(t);
                    if(tN!=null){
                        num -= (tN==0?1:0);
                        target.put(t, tN+1);
                    }
                }
            }
            return false;
        }
    }
}
